package com.aqie.hard.doublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 42 接雨水 todo
 */
public class Trap {
    /**
     * 1, 暴力  109ms
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) { //Search the left part for max bar size
                max_left = Math.max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) { //Search the right part for max bar size
                max_right = Math.max(max_right, height[j]);
            }
            ans += Math.min(max_left, max_right) - height[i];
        }
        return ans;
    }

    /**
     * 2, 4ms 动态规划 O(N)
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        int ans = 0;
        int size = height.length;
        List<Integer> left_max = Arrays.asList(new Integer[size]);
        List<Integer> right_max = Arrays.asList(new Integer[size]);

        left_max.set(0, height[0]);
        for (int i = 1; i < size; i++) {
            left_max.set(i, Math.max(height[i], left_max.get(i - 1)));
        }
        right_max.set(size - 1, height[size - 1]);

        for (int i = size - 2; i >= 0; i--) {
            right_max.set(i, Math.max(height[i], right_max.get(i + 1)));
        }
        for (int i = 1; i < size - 1; i++) {
            ans += Math.min(left_max.get(i), right_max.get(i)) - height[i];
        }
        return ans;
    }

    /**
     * 3, 栈  17ms O(N)
     * @param height
     * @return
     */
    public int trap3(int[] height) {
        int ans = 0, current = 0;
        Stack<Integer> st = new Stack<>();
        while (current < height.length) {
            while (!st.empty() && height[current] > height[st.peek()]) {
                int top = st.peek();
                st.pop();
                if (st.empty())
                    break;
                int distance = current - st.peek() - 1;
                int bounded_height = Math.min(height[current], height[st.peek()]) - height[top];
                ans += distance * bounded_height;
            }
            st.push(current++);
        }
        return ans;
    }

    /**
     * 4， 双指针  3ms  O(N)
     * @param height
     * @return
     */
    public int trap4(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max){
                    left_max = height[left];
                }else {
                    ans += (left_max - height[left]);
                }
                ++left;
            } else {
                if (height[right] >= right_max){
                    right_max = height[right];
                }else{
                    ans += (right_max - height[right]);
                }

                --right;
            }
        }
        return ans;
    }



    public static void main(String[] args) {
        int[] arr = {0,1,0,2,1,0,1,3,2,1,2,1};

    }
}
